package xyz.scootaloo.oj.leetcode

import cn.hutool.core.lang.Console
import org.junit.Test

/**
 * @author flutterdash@qq.com
 * @since 2021/5/1 8:44
 */
class P240 {

    fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
        val row = matrix.size
        val column = matrix[0].size

        if (target < matrix[0][0] || target > matrix[row - 1][column - 1])
            return false

        return if (row > column) {
            searchByColumn(matrix, row, column, target)
        } else {
            searchByRow(matrix, row, column - 1, target)
        }
    }

    private fun searchByRow(matrix: Array<IntArray>, row: Int, column: Int, target: Int): Boolean {
        for (r in 0 until row) {
            if (target < matrix[r][0])
                return false
            if (target >= matrix[r][0] && target <= matrix[r][column]) {
                if (matrix[r].binarySearch(target) >= 0)
                    return true
            }
        }
        return false
    }

    private fun searchByColumn(matrix: Array<IntArray>, row: Int, column: Int, target: Int): Boolean {
        for (c in 0 until column) {
            if (target < matrix[0][c])
                return false
            if (target >= matrix[0][c] && target <= matrix[row - 1][c]) {
                if (binarySearchColumn(matrix, row, c, target))
                    return true
            }
        }
        return false
    }

    private fun binarySearchColumn(
        matrix: Array<IntArray>,
        row: Int, column: Int,
        target: Int
    ): Boolean {
        var upper = 0
        var lower = row - 1
        var mid: Int
        var midValue: Int
        while (upper <= lower) {
            if (lower - upper <= 5) {
                return quickSearch(matrix, column, upper, lower, target)
            }
            mid = (upper + lower).shr(1)
            midValue = matrix[mid][column]
            if (midValue == target)
                return true
            if (midValue > target) {
                lower = mid - 1
            } else {
                upper = mid + 1
            }
        }

        return false
    }

    private fun quickSearch(
        matrix: Array<IntArray>,
        column: Int,
        columnFrom: Int,
        columnLimit: Int,
        target: Int
    ): Boolean {
        for (pos in columnFrom..columnLimit) {
            if (matrix[pos][column] == target)
                return true
        }
        return false
    }

    @Test
    fun test0() {
        val input = arrayOf(
            intArrayOf(1, 4, 7, 11, 15),
            intArrayOf(2, 5, 8, 12, 19),
            intArrayOf(3, 6, 9, 16, 22),
            intArrayOf(10, 13, 14, 17, 24),
            intArrayOf(18, 21, 23, 26, 30)
        )
        Console.log(searchMatrix(input, 5))
    }

    @Test
    fun test1() {
        val input = arrayOf(
            intArrayOf(-5)
        )
        Console.log(searchMatrix(input, -5))
    }

}
